Best Time to Buy and Sell Stock III

Say you have an array for which the i-th element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Solution:

  1. public class Solution {
  2.   public int maxProfit(int[] prices) {
  3.     if (prices == null || prices.length == 0) { 
  4.       return 0;
  5.     }
  7.     int n = prices.length;
  8.     int profit = 0;
  10.     // scan from left
  11.     // left[i] keeps the max profit from 0 to i
  12.     int[] left = new int[n];
  13.     int min = prices[0];
  15.     for (int i = 1; i < n; i++) {
  16.       left[i] = Math.max(left[i - 1], prices[i] - min);
  17.       min = Math.min(min, prices[i]);
  18.     }
  20.     // scan from right
  21.     // right[i] keeps the max profit from i to n - 1
  22.     int[] right = new int[n];
  23.     int max = prices[n - 1];
  25.     for (int i = n - 2; i >= 0; i--) {
  26.       right[i] = Math.max(right[i + 1], max - prices[i]);
  27.       max = Math.max(max, prices[i]);
  29.       profit = Math.max(profit, left[i] + right[i]);
  30.     }
  32.     return profit;
  33.   }
  34. }

Time complexity: O(n)